import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public abstract class Heap<T extends Comparable<T>> {
	private static final Comparable<?>[] empty = new Comparable[0];
	@SuppressWarnings("unchecked")
	protected T[] objs = (T[])empty;
	protected int size;

	public int size() {
		return size;
	}

	public void clear() {
		Arrays.fill(objs, 0, size, null);
		size = 0;
	}

	public T get(int i) {
		return objs[i];
	}

	public abstract void push(T obj);

	public abstract T pop();

	static void ASSERT(boolean b) {
		if (!b)
			throw new AssertionError();
	}

	static void testN(Heap<Integer> h, int n) {
		ThreadLocalRandom r = ThreadLocalRandom.current();
		int aa = 0;
		for (int i = 0; i < n; i++) {
			int a = r.nextInt(n);
			h.push(a);
			aa += a;
		}
		ASSERT(h.size() == n);
		int a = -1, bb = 0;
		for (int i = 0; i < n; i++) {
			int b = h.pop();
			ASSERT(a <= b);
			a = b;
			bb += b;
		}
		ASSERT(h.size() == 0);
		ASSERT(h.pop() == null);
		ASSERT(aa == bb);
		for (int i = 0; i < n; i++)
			ASSERT(h.get(i) == null);
	}

	static void test(Heap<Integer> h) {
		ASSERT(h.size() >= 0);
		h.clear();
		ASSERT(h.size() == 0);
		ASSERT(h.pop() == null);
		for (int n = 0; n <= 5; n++)
			testN(h, n);
		for (int n = 10; n <= 1000000; n *= 10)
			testN(h, n);
		System.out.format("test %s OK!\n", h.getClass().getSimpleName());
	}

	static void benchmarkN(Heap<Integer> h, int n) {
		ThreadLocalRandom r = ThreadLocalRandom.current();
		long t = System.nanoTime();
		for (int i = 0; i < n; i++)
			h.push(r.nextInt(n));
		int a = 0;
		for (int i = 0; i < n; i++)
			a += h.pop();
		t = System.nanoTime() - t;
		System.out.format("%10s(%7d):%10d ns, %d\n", h.getClass().getSimpleName(), n, t, a);
	}

	static void benchmark(Heap<Integer> h) {
		h.clear();
		for (int n = 10; n <= 1000000; n *= 10)
			benchmarkN(h, n);
	}

	public static void main(String[] ignoredArgs) {
		BinHeap<Integer> bh = new BinHeap<>();
		QuadHeap<Integer> qh = new QuadHeap<>();
		OctHeap<Integer> oh = new OctHeap<>();
		test(bh);
		test(qh);
		test(oh);
		System.out.println("---");
		for (int i = 0; i < 5; i++) {
			benchmark(bh);
			benchmark(qh);
			benchmark(oh);
			System.out.println("---");
		}
	}
}

// [0 1  2  3   4   5   6   7    ...]
// [R R0 R1 R00 R01 R10 R11 R000 ...]
// parentIndex = (childIndex-1)/2
// childIndex = parentIndex*2+(1|2)
class BinHeap<T extends Comparable<T>> extends Heap<T> {
	@Override
	public void push(T obj) {
		if (obj == null)
			throw new NullPointerException();
		T[] os = objs;
		int i = size;
		if (i == os.length)
			objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));
		size = i + 1;
		while (i > 0) { // sift up
			int j = (i - 1) >> 1;
			T po = os[j];
			if (obj.compareTo(po) >= 0)
				break;
			os[i] = po;
			i = j;
		}
		os[i] = obj;
	}

	@Override
	public T pop() {
		int n = size;
		if (n == 0)
			return null;
		T[] os = objs;
		T r = os[0], obj = os[--n];
		os[n] = null;
		size = n;
		if (n > 0) {
			int i = 0;
			for (T c, d; ; ) { // sift down
				int j = i * 2 + 1, k = j + 1;
				if (k < n) { // full children
					if ((c = os[j]).compareTo(d = os[k]) >= 0) {
						c = d;
						j = k;
					}
				} else if (j < n) // part of children
					c = os[j];
				else // no child
					break;
				if (c.compareTo(obj) >= 0)
					break;
				os[i] = c;
				i = j;
			}
			os[i] = obj;
		}
		return r;
	}
}

// [0 1  2  3  4  5   6   7   8   9   ...]
// [R R0 R1 R2 R3 R00 R01 R02 R03 R10 ...]
// parentIndex = (childIndex-1)/4
// childIndex = parentIndex*4+(1|2|3|4)
class QuadHeap<T extends Comparable<T>> extends Heap<T> {
	@Override
	public void push(T obj) {
		if (obj == null)
			throw new NullPointerException();
		T[] os = objs;
		int i = size;
		if (i == os.length)
			objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));
		size = i + 1;
		while (i > 0) { // sift up
			int j = (i - 1) >> 2;
			T po = os[j];
			if (obj.compareTo(po) >= 0)
				break;
			os[i] = po;
			i = j;
		}
		os[i] = obj;
	}

	@Override
	public T pop() {
		int n = size;
		if (n == 0)
			return null;
		T[] os = objs;
		T r = os[0], obj = os[--n];
		os[n] = null;
		size = n;
		if (n > 0) {
			int i = 0;
			for (T c, d; ; ) { // sift down
				int j = i * 4 + 1, k;
				if (j + 3 < n) { // full children
					c = os[j];
					if (c.compareTo(d = os[k = j + 1]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
				} else if (j < n) { // part of children
					c = os[j];
					if ((k = j + 1) < n) {
						if (c.compareTo(d = os[k]) >= 0) {
							c = d;
							j = k;
						}
						if (++k < n && c.compareTo(d = os[k]) >= 0) {
							c = d;
							j = k;
						}
					}
				} else // no child
					break;
				if (c.compareTo(obj) >= 0)
					break;
				os[i] = c;
				i = j;
			}
			os[i] = obj;
		}
		return r;
	}
}

// [0 1  2  3  4  5  6  7  8  9   ...]
// [R R0 R1 R2 R3 R4 R5 R6 R7 R00 ...]
// parentIndex = (childIndex-1)/8
// childIndex = parentIndex*8+(1|2|3|4|5|6|7|8)
class OctHeap<T extends Comparable<T>> extends Heap<T> {
	@Override
	public void push(T obj) {
		if (obj == null)
			throw new NullPointerException();
		T[] os = objs;
		int i = size;
		if (i == os.length)
			objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));
		size = i + 1;
		while (i > 0) { // sift up
			int j = (i - 1) >> 3;
			T po = os[j];
			if (obj.compareTo(po) >= 0)
				break;
			os[i] = po;
			i = j;
		}
		os[i] = obj;
	}

	@Override
	public T pop() {
		int n = size;
		if (n == 0)
			return null;
		T[] os = objs;
		T r = os[0], obj = os[--n];
		os[n] = null;
		size = n;
		if (n > 0) {
			int i = 0;
			for (T c, d; ; ) { // sift down
				int j = i * 8 + 1, k;
				if (j + 7 < n) { // full children
					c = os[j];
					if (c.compareTo(d = os[k = j + 1]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
					if (c.compareTo(d = os[++k]) >= 0) {
						c = d;
						j = k;
					}
				} else if (j < n) { // part of children
					c = os[j];
					if ((k = j + 1) < n) {
						if (c.compareTo(d = os[k]) >= 0) {
							c = d;
							j = k;
						}
						if (++k < n) {
							if (c.compareTo(d = os[k]) >= 0) {
								c = d;
								j = k;
							}
							if (++k < n) {
								if (c.compareTo(d = os[k]) >= 0) {
									c = d;
									j = k;
								}
								if (++k < n) {
									if (c.compareTo(d = os[k]) >= 0) {
										c = d;
										j = k;
									}
									if (++k < n) {
										if (c.compareTo(d = os[k]) >= 0) {
											c = d;
											j = k;
										}
										if (++k < n && c.compareTo(d = os[k]) >= 0) {
											c = d;
											j = k;
										}
									}
								}
							}
						}
					}
				} else // no child
					break;
				if (c.compareTo(obj) >= 0)
					break;
				os[i] = c;
				i = j;
			}
			os[i] = obj;
		}
		return r;
	}
}
